Public key digital signatures are important for secure exchange of information between plural parties, for example between computers or mobile devices, or between a smart card and a terminal.
In the late 1990s two of the inventors hereof proposed authentication and signature schemes based on the problem of recovering a polynomial with tightly concentrated coefficients given a small number of evaluations of that polynomial. The heuristic justification for the security of the scheme was that the uncertainty principle severely restricts how concentrated a signal can be in two mutually incoherent bases.
An early incarnation of that scheme is described in U.S. Pat. No. 6,076,163. and a later version, called PASS-2 was described in Hoffstein, J., Silverman, J. H.: Polynomial Rings and Efficient Public Key Authentication II. In: Lam, K. Y., Shparlikski, I., Wang, H., Xing, C. (eds.), Cryptography and Computational Number Theory, Progress in Computer Science and Applied Logic, vol. 20, pp. 269-286, Birkhauser (2001). A summary description of the PASS-2 technique is included as part of the attached Appendix I. The original PASS protocols, which are also described in Appendix I, include the following: Given a message μ, a secret key f with small norm, and a public key {circumflex over (f)}lΩ=fΩf, equal to the evaluations of f at the values contained in the set Ω, the objective is to construct a signature that mixes f and μ and can be verified by means of {circumflex over (f)}lΩ. A prototype of this was presented in the above-referenced U.S. Pat. No. 6,076,163.
To sign, the signer                Computes and keeps secret a short polynomial gεRq and reveals the commitment ĝ/Ω=FΩg.        Computes and reveals a short challenge polynomial cεRq from Hash(ĝlΩ,μ).        Computes and reveals h=g*(f+c).        
To verify, the verifier                Verifies that h has norm less than a specific upper bound.        Verifies that c=Hash(ĥlΩ/({circumflex over (f)}lΩ+ĉlΩ),μ)        
The first condition for verification is met because|g*(f+c)|≈|g∥f+c|. The fact that |f|, |g|, |c| are small thus implies that |h| is small. The second condition is true because Ω is a ring homomorphism.
To forge a signature, a third party would need to produce an h which is short, and which satisfies the required evaluations at points in Ω. It is conjectured that finding such an h is no easier than solving the associated closest vector problem.
The difficulty with this PASS prototype is that a transcript of signatures produced by a single signer on any set of messages leaks information about that signer's secret key. This is explained further in Appendix I.
The problem with PASS was not that individual signatures leaked information about the secret key, but rather that an average over a collection of signatures would converge to a secret key dependent value.
It is among the objects of the present invention to address and solve this type of vulnerability in certain public key digital signature techniques.